/*******************************************************************
    Copyright (C) 2009 FreakLabs
    All rights reserved.
    
    Redistribution and use in source and binary forms, with or without
    modification, are permitted provided that the following conditions
    are met:
 
    1. Redistributions of source code must retain the above copyright
       notice, this list of conditions and the following disclaimer.
    2. Redistributions in binary form must reproduce the above copyright
       notice, this list of conditions and the following disclaimer in the
       documentation and/or other materials provided with the distribution.
    3. Neither the name of the the copyright holder nor the names of its contributors
       may be used to endorse or promote products derived from this software
       without specific prior written permission.
    4. This software is subject to the additional restrictions placed on the
       Zigbee Specification's Terms of Use.
    
    THIS SOFTWARE IS PROVIDED BY THE THE COPYRIGHT HOLDERS AND CONTRIBUTORS ``AS IS'' AND
    ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
    IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
    ARE DISCLAIMED.  IN NO EVENT SHALL THE INSTITUTE OR CONTRIBUTORS BE LIABLE
    FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
    DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
    OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
    HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
    LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
    OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
    SUCH DAMAGE.
 
    Originally written by Christopher Wang aka Akiba.
    Please post support questions to the FreakLabs forum.

*******************************************************************/
/*!
    \file nwk_rte_mesh.c
    \ingroup nwk
    \brief NWK mesh routing

    This file contains functions that implement Zigbee mesh routing.
    The mesh routing is based on AODV which uses route requests, replies,
    and path costs to determine the best route for transmission. The
    sequence goes something like this:

    - A route request command frame is generated by the source node and
    broadcast to the network.
    - The route request propagates over the whole network and eventually
    reaches the destination node.
    - The destination node will send a route reply command frame to the node
    that sent the request.
    - The node that received the route reply will unicast it to the node
    that sent it the route request.
    - The path will be followed until it reaches the originating node.
    The originating node will add the route to its routing table.
*/
/*******************************************************************/
#include "freakz.h"

/**************************************************************************/
/*!
        List head for the route request list used in route discovery. When a route
        discovery is performed, we generate a route request and broadcast it 
        across the whole network. If we get multiple frames that need to be 
        forwarded to different destinations, then we need to send route requests
        out for each destination. The route requests get stored in this list which
        allows us to perform route discovery for multiple destinations simultaneously.
*/
/**************************************************************************/
LIST(rreq_list);
static struct ctimer rreq_tmr;  ///< Callback timer for route request. RREQ retried on timeout.

/**************************************************************************/
/*!
    Init the route request list. The route request list will be used when
    we have multiple route discoveries in progress simultaneously.
*/
/**************************************************************************/
void nwk_rte_mesh_init()
{
    list_init(rreq_list);
    nwk_rte_mesh_periodic(NULL);
}

/**************************************************************************/
/*!
    Find a free route request entry and add it to the route request list.
*/
/**************************************************************************/
static mem_ptr_t *nwk_rte_mesh_rreq_alloc()
{
    mem_ptr_t *mem_ptr;

    if ((mem_ptr = mem_heap_alloc(sizeof(rreq_t))) != NULL)
    {
        list_add(rreq_list, mem_ptr);
    }
    return mem_ptr;
}

/**************************************************************************/
/*!
    Remove a rreq entry from the list and free it.
*/
/**************************************************************************/
static void nwk_rte_mesh_rreq_free(mem_ptr_t *mem_ptr)
{
    if (mem_ptr)
    {
        list_remove(rreq_list, mem_ptr);
        mem_heap_free(mem_ptr);
    }
}

/**************************************************************************/
/*!
    Generate and send a route request command frame. The command info will
    be generated from the specified command data struct argument. The header
    will be generated by the rest of the arguments. We will also enter a route
    request entry into the route request list so we can track this request's info.
*/
/**************************************************************************/
static void nwk_rte_mesh_send_rreq(nwk_cmd_t *cmd, U16 src_addr, U8 path_cost, U8 radius)
{
    nwk_nib_t *nib = nwk_nib_get();
    nwk_hdr_t hdr;
    buffer_t *buf;
    mem_ptr_t *mem_ptr;

    // prepare route request
    cmd->cmd_frm_id     = NWK_CMD_RTE_REQ;
    cmd->rreq.cmd_opts  = 0;
    cmd->rreq.path_cost = path_cost;

    // prepare route request nwk frame header
    hdr.nwk_frm_ctrl.frame_type = NWK_CMD_FRM;
    hdr.nwk_frm_ctrl.disc_route = false;
    hdr.src_addr                = src_addr;
    hdr.dest_addr               = NWK_BROADCAST_ROUTERS_COORD;
    hdr.radius                  = radius;
    hdr.seq_num                 = nib->seq_num;

    // copy the hdr and cmd structs. we'll use them later for retransmission.
    if ((mem_ptr = nwk_rte_mesh_rreq_alloc()) != NULL)
    {
        RREQ_ENTRY(mem_ptr)->originator    = src_addr;
        RREQ_ENTRY(mem_ptr)->radius        = radius;
        RREQ_ENTRY(mem_ptr)->retries       = 0;
        RREQ_ENTRY(mem_ptr)->expiry        = 1;
        memcpy(&RREQ_ENTRY(mem_ptr)->cmd, cmd, sizeof(nwk_cmd_t));
    }

    // gen the nwk frame and send it out
    BUF_ALLOC(buf, TX);
    nwk_gen_cmd(buf, cmd);
    debug_dump_nwk_cmd(cmd);
    nwk_fwd(buf, &hdr);
}

/**************************************************************************/
/*!
    Generate and send a route reply command frame. The command and header info
    is generated from the information provided by the arguments.
*/
/**************************************************************************/
static void nwk_rte_mesh_send_rrep(U8 rreq_id, U16 originator, U16 responder, U8 path_cost, U16 sender_addr)
{
    nwk_nib_t *nib = nwk_nib_get();
    nwk_hdr_t hdr;
    nwk_cmd_t cmd;
    buffer_t *buf;

    cmd.cmd_frm_id              = NWK_CMD_RTE_REP;
    cmd.rrep.cmd_opts           = 0x00;
    cmd.rrep.rreq_id            = rreq_id;
    cmd.rrep.originator         = originator;
    cmd.rrep.responder          = responder;
    cmd.rrep.path_cost          = path_cost;

    hdr.nwk_frm_ctrl.frame_type = NWK_CMD_FRM;
    hdr.nwk_frm_ctrl.disc_route = false;
    hdr.src_addr                = nib->short_addr;
    hdr.dest_addr               = sender_addr;
    hdr.radius                  = (U8)(nib->max_depth << 1);
    hdr.seq_num                 = nib->seq_num;

    BUF_ALLOC(buf, TX);
    nwk_gen_cmd(buf, &cmd);
    debug_dump_nwk_cmd(&cmd);
    nwk_fwd(buf, &hdr);
}

/**************************************************************************/
/*!
    This function sets up a route discovery operation by initializing the discovery
    info. Once the data is initialized, we will call the rreq handler which is
    where the real route discovery starts.
*/
/**************************************************************************/
void nwk_rte_mesh_disc_start(U16 dest_addr)
{
    nwk_nib_t *nib = nwk_nib_get();
    nwk_hdr_t nwk_hdr;
    mac_hdr_t mac_hdr;
    nwk_cmd_t cmd;

    nwk_hdr.mac_hdr     = &mac_hdr;

    cmd.rreq.rreq_id    = nib->rreq_id++;
    cmd.rreq.dest_addr  = dest_addr;
    cmd.rreq.cmd_opts   = 0;
    cmd.rreq.path_cost  = 0;

    nwk_hdr.radius      = (U8)(nib->max_depth << 1);   // default radius = 2 * max depth
    nwk_hdr.src_addr    = mac_hdr.src_addr.short_addr = nib->short_addr;

    nwk_rte_mesh_rreq_handler(&nwk_hdr, &cmd);
}

/**************************************************************************/
/*!
    Process an incoming route request and decide if it needs to be forwarded
    or a route reply needs to be generated. This function will check the
    discovery table to see if we received the same route request previously.
    If we did, then it will compare the path cost to see if the incoming route
    request has a more efficient path. If so, then it will replace the discovery
    entry info with the info from this route request.

    If its a new route request, then it will create a route discovery entry and a
    routing table entry. It will then check to see if its the destination. If so, then
    a route reply will be sent. Otherwise, it will relay the route request via
    broadcast.
*/
/**************************************************************************/
void nwk_rte_mesh_rreq_handler(const nwk_hdr_t *hdr_in, nwk_cmd_t *cmd_in)
{
    nwk_pcb_t *pcb = nwk_pcb_get();
    nwk_nib_t *nib = nwk_nib_get();
    mem_ptr_t *disc_mem_ptr;
    mem_ptr_t *rte_mem_ptr;
    U8 path_cost;
    address_t dest_addr;

    dest_addr.mode          = SHORT_ADDR;
    dest_addr.short_addr    = cmd_in->rreq.dest_addr;

    // if we are originating the rreq, then set the path cost to zero. otherwise add the static path cost.
    // later on, we need to figure out a better way to generate path costs.
    path_cost = (hdr_in->src_addr != nib->short_addr) ? cmd_in->rreq.path_cost + NWK_STATIC_PATH_COST: cmd_in->rreq.path_cost;

    // check if route discovery table entry exists.
    if ((disc_mem_ptr = nwk_rte_disc_find(cmd_in->rreq.rreq_id, hdr_in->src_addr)) != NULL)
    {
        // if the path cost is less than the fwd cost, then update the entry
        if (path_cost < DISC_ENTRY(disc_mem_ptr)->fwd_cost)
        {
            // If the path cost is less than the fwd cost, then replace the disc table disc_entry path
            // with this path.
            DISC_ENTRY(disc_mem_ptr)->sender_addr  = hdr_in->mac_hdr->src_addr.short_addr;
            DISC_ENTRY(disc_mem_ptr)->fwd_cost     = path_cost;
        }
        else
        {
            // since we already have a discovery entry for this rreq and there's no benefit in cost, drop the rreq
            pcb->drop_rreq_frm++;
            return;
        }
    }
    else
    {
        // add the new discovery entry to the discovery table
        nwk_rte_disc_add_new(cmd_in->rreq.rreq_id, hdr_in->src_addr, hdr_in->mac_hdr->src_addr.short_addr, hdr_in->dest_addr, path_cost);
    }

    // get the route entry for this rreq if it exists. otherwise, create a new entry.
    if ((rte_mem_ptr = nwk_rte_tbl_find(cmd_in->rreq.dest_addr)) != NULL)
    {
        // if the route entry isn't active or active but requires validation, then change it to discovery underway.
        if ((RTE_ENTRY(rte_mem_ptr)->status != NWK_ACTIVE) && (RTE_ENTRY(rte_mem_ptr)->status != NWK_VALIDATION_UNDERWAY))
        {
            RTE_ENTRY(rte_mem_ptr)->status = NWK_DISCOVERY_UNDERWAY;
        }
    }
    else
    {
        nwk_rte_tbl_add_new(cmd_in->rreq.dest_addr, NWK_DISCOVERY_UNDERWAY);
    }

    // now check to see if the route request destination was meant for us. If so, then prepare a route reply.
    if ((cmd_in->rreq.dest_addr == nib->short_addr) || nwk_neighbor_tbl_addr_exists(&dest_addr))
    {
        // send out the route reply
        nwk_rte_mesh_send_rrep(cmd_in->rreq.rreq_id, hdr_in->src_addr, cmd_in->rreq.dest_addr,
                               path_cost, hdr_in->mac_hdr->src_addr.short_addr);
    }
    else
    {
        // fwd the rreq
        nwk_rte_mesh_send_rreq(cmd_in, hdr_in->src_addr, path_cost, hdr_in->radius);
    }
}

/**************************************************************************/
/*!
    Process an incoming route reply and decide if it needs to be forwarded.

    First we need to make sure that we have a discovery table and routing table
    entry for this route reply. If not, then discard the route reply. Also, if
    the path cost is greater than what we currently have in our discovery table
    entry, then also discard this reply since its a less efficient path.

    If this route reply is for us, then end the route discovery process and send out
    any frames that are buffered in the pending list. Otherwise, forward the route
    reply to the sender of the route request as recorded in the discovery
    table entry.
*/
/**************************************************************************/
void nwk_rte_mesh_rrep_handler(const nwk_hdr_t *hdr_in, const nwk_cmd_t *cmd_in)
{
    nwk_pcb_t *pcb = nwk_pcb_get();
    nwk_nib_t *nib = nwk_nib_get();
    mem_ptr_t *disc_mem_ptr;
    mem_ptr_t *rte_mem_ptr;
    U8 path_cost;

    disc_mem_ptr  = nwk_rte_disc_find(cmd_in->rrep.rreq_id, cmd_in->rrep.originator);
    rte_mem_ptr   = nwk_rte_tbl_find(cmd_in->rrep.responder);
    path_cost   = cmd_in->rrep.path_cost + NWK_STATIC_PATH_COST;

    // if the rte entry or discovery entry doesn't exist or the path cost is not less than the current resid cost, then drop
    // the rrep.
    if ((!rte_mem_ptr) || (!disc_mem_ptr) || (path_cost >= DISC_ENTRY(disc_mem_ptr)->resid_cost))
    {
        if (!rte_mem_ptr || !disc_mem_ptr)
        {
            nwk_rte_tbl_free(rte_mem_ptr);
            nwk_rte_disc_free(disc_mem_ptr);
        }
        pcb->drop_rrep_frm++;
        return;
    }

    // we've met all the criteria to keep the rrep. that means we should update the rrep and disc entry.
    // any time we update the next hop in the rte entry, we need to reset the discovery entry's expiry
    DISC_ENTRY(disc_mem_ptr)->resid_cost  = path_cost;
    DISC_ENTRY(disc_mem_ptr)->expiry      = NWK_RTE_DISC_TIME;
    RTE_ENTRY(rte_mem_ptr)->next_hop     = hdr_in->mac_hdr->src_addr.short_addr;

    // update the entry to validation underway. once we send an actual frame through it, then we can change
    // it to NWK_VALIDATION_UNDERWAY.
    RTE_ENTRY(rte_mem_ptr)->status = (RTE_ENTRY(rte_mem_ptr)->status == NWK_DISCOVERY_UNDERWAY) ?
                                      NWK_VALIDATION_UNDERWAY :
                                      RTE_ENTRY(rte_mem_ptr)->status;

    // check if the rrep is meant for us.
    if (cmd_in->rrep.originator == nib->short_addr)
    {
        // send out pending xfers
        nwk_pend_send_pending();
        DBG_PRINT("\nNWK_RTE_MESH: Route established.\n");
        return;
    }

    // forward the route reply
    nwk_rte_mesh_send_rrep(cmd_in->rrep.rreq_id, cmd_in->rrep.originator, cmd_in->rrep.responder,
                           path_cost, DISC_ENTRY(disc_mem_ptr)->sender_addr);
}


/**************************************************************************/
/*!
    This function handles a route request expiration. There are two cases we
    need to be concerned about. If we are originating or forwarding the route
    discovery, then we need to send the rreq NWK_RREQ_RETRIES times with a
    spacing of NWK_RREQ_RETRY_INTERVAL. We also need to jitter the broadcasts by
    the following amount so as not to flood the network with broadcast frames.
      - jitter =  2 * ((rand() % (NWK_MAX_RREQ_JITTER - NWK_MIN_RREQ_JITTER)) + NWK_MIN_RREQ_JITTER).

    \note Although not very network efficient, all route requests are required
    to be sent NWK_RREQ_RETRIES times according to the Zigbee spec.
*/
/**************************************************************************/
void nwk_rte_mesh_resend_rreq(mem_ptr_t *mem_ptr)
{
    nwk_nib_t *nib = nwk_nib_get();
    nwk_hdr_t hdr;
    buffer_t *buf;

    if (mem_ptr)
    {
        RREQ_ENTRY(mem_ptr)->retries++;
        if (RREQ_ENTRY(mem_ptr)->retries < NWK_RREQ_RETRIES)
        {
            DBG_PRINT("NWK_RTE_MESH_RESEND_RREQ: Sending.\n");

            // reset the rreq expiry
            RREQ_ENTRY(mem_ptr)->expiry = 1;

            // we need to re-send NWK_RREQ_RETRIES times with a jitter imposed on the resend. do a busy wait for the jitter.
            busy_wait(drvr_get_rand() % NWK_BRC_JITTER);

            // generate and send out the rreq
            hdr.nwk_frm_ctrl.frame_type = NWK_CMD_FRM;
            hdr.nwk_frm_ctrl.disc_route = false;
            hdr.src_addr                = RREQ_ENTRY(mem_ptr)->originator;
            hdr.dest_addr               = NWK_BROADCAST_ROUTERS_COORD;
            hdr.radius                  = RREQ_ENTRY(mem_ptr)->radius;
            hdr.seq_num                 = nib->seq_num++;

            BUF_ALLOC(buf, TX);
            nwk_gen_cmd(buf, &RREQ_ENTRY(mem_ptr)->cmd);
            nwk_fwd(buf, &hdr);
            return;
        }

        // we're finished with this rreq. retire it.
        DBG_PRINT("NWK_RTE_MESH: Route Request Finished.\n");
        nwk_rte_mesh_rreq_free(mem_ptr);
    }
}

/**************************************************************************/
/*!
    This is a periodic function called by the slow clock. It is used to expire
    the route request entry. Each time it is called, it will decrement the
    expiry in the route request list entry.
*/
/**************************************************************************/
//lint -e{715} Info 715: Symbol 'ptr' not referenced
//lint -e{818} Info 818: Pointer parameter ptr' could be declared as pointing to const
void nwk_rte_mesh_periodic(void *ptr)
{
    mem_ptr_t *mem_ptr;

    for (mem_ptr = list_head(rreq_list); mem_ptr != NULL; mem_ptr = mem_ptr->next)
    {
        if (RREQ_ENTRY(mem_ptr)->expiry == 0)
        {
            nwk_rte_mesh_resend_rreq(mem_ptr);
        }
        else
        {
            RREQ_ENTRY(mem_ptr)->expiry--;
        }
    }
    ctimer_set(&rreq_tmr, NWK_RREQ_RETRY_INTERVAL, nwk_rte_mesh_periodic, NULL);
}

/**************************************************************************/
/*!
    Stop the route request periodic timer.
*/
/**************************************************************************/
void nwk_rte_mesh_stop_tmr()
{
    ctimer_stop(&rreq_tmr);
}
